package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * leetcode 543 二叉树的直径
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/9 10:16
 */
public class E543 {

    /**
     * <h3>方法一：层序遍历每个节点的最大直径，同理可换成深度优先遍历，效率低</h3>
     * @param root 二叉树的根节点
     * @return 二叉树的直径
     */
    @SuppressWarnings("all")
    public int diameterOfBinaryTree1(TreeNode root) {
        if (root == null)
            return 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int diameter = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null){
                    queue.offer(poll.left);
                }
                if (poll.right != null){
                    queue.offer(poll.right);
                }
                int currDiameter = depth1(poll.left) + depth1(poll.right); // 这里计算的深度是从1开始计数
                diameter = Math.max(diameter, currDiameter);
            }
        }
        return diameter;
    }

    /**
     * <h3>方法二：直接递归求最大直径，性能也一般</h3>
     * @param root 二叉树的根节点
     * @return 二叉树的直径
     */
    public int diameterOfBinaryTree2(TreeNode root) {
        if (root == null)
            return 0;
        // 递的时候求左子树的最大直径和右子树的最大直径
        int left = diameterOfBinaryTree2(root.left);
        int right = diameterOfBinaryTree2(root.right);
        // 和当前树的过根节点的直径比较，得出当前树的最大直径
        int curr = depth1(root.left) + depth1(root.right);
        // 归的时候返回当前树的最大直径
        return Math.max(curr, Math.max(left, right));
    }

    /**
     * 计算节点深度，从1开始计数。
     * <strong>其实可以发现方法一还是方法二都会有很多重复调用此方法，
     * 理论上记忆法和动态规划是可以的，但是不知道二叉树的节点个数
     * 记忆数组或者动态数组创建较难</strong>
     * @param root 当前树的根节点
     * @return 节点深度
     */
    private int depth1(TreeNode root){
        if (root == null)
            return 0;
        return Math.max(depth1(root.left), depth1(root.right)) + 1;
    }

    private int diameter = 0; // 存储最大直径

    /**
     * <h3>方法三：在求深度的时候直接得出最大直径，效率最高，因为只用进行一次深度优先遍历</h3>
     * @param root 二叉树的根节点
     * @return 二叉树的直径
     */
    @SuppressWarnings("all")
    public int diameterOfBinaryTree3(TreeNode root) {
        if (root == null)
            return 0;
        depth2(root);
        return diameter;
    }

    /**
     * 求深度的同时记录最大直径
     * @param root 二叉树的根节点
     * @return 节点深度
     */
    private int depth2(TreeNode root){
        if (root == null)
            return 0;
        int left = depth2(root.left);
        int right = depth2(root.right);
        diameter = Math.max(diameter, left + right);
        return Math.max(left, right) + 1;
    }
}
